\documentclass[12pt]{article}
\usepackage{amsfonts}
%\documentstyle[12pt,amsfonts]{article}
%\documentstyle{article}

\setlength{\topmargin}{-.5in}
\setlength{\oddsidemargin}{0 in}
\setlength{\evensidemargin}{0 in}
\setlength{\textwidth}{6.5truein}
\setlength{\textheight}{8.5truein}
%\input ../basicmath/basicmathmac.tex
%
%\input ../adgeomcs/lamacb.tex
\input mac.tex
\input mathmac.tex

\def\fseq#1#2{(#1_{#2})_{#2\geq 1}}
\def\fsseq#1#2#3{(#1_{#3(#2)})_{#2\geq 1}}
\def\qleq{\sqsubseteq}

%
\begin{document}
\begin{center}
\fbox{{\Large\bf Spring, 2009 \hspace*{0.4cm} CIS 511}}\\
\vspace{1cm}
{\Large\bf Introduction to the Theory of Computation\\
Homework 3\\}
\vspace{0.5cm}
\textbf{Jian Chang, Sanjian Chen, Yeming Fang}\\
\vspace{0.2cm}
\itshape{\{jianchan,sanjian,yemingf\}@cis.upenn.edu}

\end{center}

\vspace {0.25cm}\noindent
{\bf Solution B1.}\\

\vspace {0.25cm}\noindent
(i) (a) ``$\rightarrow$'' direction: prove that $U\subseteq \natnums\ \rightarrow
U = F \cup \bigcup_{i = 1}^k \, \{m_i + jp\mid j\in \natnums\}$.\\

Prove: $U\subseteq \natnums \rightarrow \exists m, p\in \natnums$, with $p \geq 1$, so that
$n\in U$ iff $n + p\in U$, for all $n\geq m$. Let $F=\{x\ |\ x \in U,\ x<m \}$. Since $U$ is a subset
of $\natnums$, it is clear that $F$ is a finite set.\\

Let $D = U - F$. Consider a $p$-partition of $\natnums$ : $P_x=\{x+jp\ |\ j \in \natnums \}, x=0,1,2 \cdots (p-1)\}$.\\

Obviously, $D$ and $P_x$ are both well-ordered. Let $m'_x$ denotes the least element of $D \cap P_x$.
Let $M = \{m'_x,x=0,1,2 \cdots (p-1)\}$, say $|M|=k$, clearly $k \leq p$.
Ascending sort all elements in $M$ and rename them as $m_1 < m_2 < \cdots < m_k < m_1 + p$.\\

Next, we prove that $U = F \cup \bigcup_{i = 1}^k \, \{m_i + jp\mid j\in \natnums\}$ in two steps:
\begin{enumerate}
  \item Prove $U \subseteq F \cup \bigcup_{i = 1}^k \, \{m_i + jp\mid j\in \natnums\}$\\
  $\forall n \in U$, if $n < m$, then $n \in F$; if $n \geq m$, accoording to the definition of $M$,
  there exists $x_i \in M,\ j \in \natnums \ni n = x_i+jp$.
  \item Prove $U \supseteq F \cup \bigcup_{i = 1}^k \, \{m_i + jp\mid j\in \natnums\}$\\
  By definition $F \subseteq U$; $\forall x \in \bigcup_{i = 1}^k \, \{m_i + jp\mid j\in \natnums\}$,
  suppose $x \in \{m_i + jp\mid j\in \natnums\}$. Notice that by definition, $m_i \in U$, and $U$ is ultimately
  periodic, so obviously $x \in U$;
\end{enumerate}

\noindent
(i) (b) ``$\leftarrow$'' direction: prove that $U\subseteq \natnums\ \leftarrow
U = F \cup \bigcup_{i = 1}^k \, \{m_i + jp\mid j\in \natnums\}$.\\

Prove: This proof is actually trivial. Since $F$ is finite, denote the greatest element of $F$ as $m-1$.
For all $n \geq m$ and $n \in U$, $n \in \bigcup_{i = 1}^k \, \{m_i + jp\mid j\in \natnums\}$. In another word, $n \in U$ iff
$n + p \in U$.

\vspace{0.25cm}\noindent
(i) (c) Example: Let $U$ be the set of all non-negative even numbers. $U=\{2k\ |\ k \in \natnums\}$.
It is trivial that $U$ is ultimately periodic with $m_1 = 2,\ p_1 = 4$ and $m_2 = 10,\ p_2 = 8$.

\vspace{0.25cm}\noindent
(ii) (a)
\begin{itemize}
  \item ``$\rightarrow$'' direction: Suppose $L$ is a regular language. In Homework 1 B5(b), we proved that if $L\subseteq \{a\}^*$ is regular language, then there there is a finite set $F\subseteq \{a\}^*$, and some strings $a^m$, $a^{p_1}, \ldots, a^{p_k}$, and $a^q\not=\epsilon$, with 
$0\leq p_1 < p_2 < \ldots < p_k < q$, such that $$L = F\cup \bigcup_{i = 1}^k a^{m + p_i}\{a^q\}^*.$$. \\

Rewrite $m_i = m+p_i, p = q $, it immediately follows that $\{m \in \natnums \mid a^m\in L\} = F \cup \bigcup_{i = 1}^k \, \{m_i + jp\mid j\in \natnums\}$, which we have proved in (i) to be ultimately periodic.
  \item ``$\leftarrow$'' direction: Suppose $\{m \in \natnums \mid a^m\in L\}$ is ultimately periodic. From (i) we know it is finite or there is a finite subset $F\subseteq \natnums$ and there are $k \leq p$ numbers $m_1, \ldots, m_k$, with $m_1 < m_2 < \cdots < m_k < m_1 + p$, and with $m_1$ the smallest element of $U$ so that for some $p \geq 1$, $n\in U$ iff $n + p\in U$, for all $n\geq m_1$, so that $\{m \in \natnums \mid a^m\in L\} = F \cup \bigcup_{i = 1}^k \, \{m_i + jp\mid j\in \natnums\}.$ Just as what we do when proving the Homework 1 B5(b), we construct a trim DFA contains a single cycle with length of $p$. We then mark all the non-cycle states denoted by finite set $F$ and all the in-cycle states denoted by $\{m_i\}$ as final states. It is trivial that such DFA accepts $L$. Therefore $L$ is regular.
\end{itemize}

\vspace{0.25cm}\noindent
(ii) (b) From the remark, we know a set is ultimately periodic iff it is semilinear. And from (ii)(a), we prove that any ultimately periodic set correspond to a regular language over one-letter alphabet$\{a\}$. Thus, we can say any semilinear set correspond to a regular language over alphabet $\{a\}$. Here, we actually build a equivalence relationship between the union, intersection and complementation operation to family of semilinear sets and those operations to regular languages. From the principle that ``the regular languages are closed under all three of the boolean operations(union, intersection, complement)'', it immediately follows that the family of semilinear sets is also closed under union, intersection and complementation. 

\vspace{0.25cm}\noindent
(iii) First we prove the following lemma:\\

\noindent
\textbf{Lemma}: If $L \subseteq \Sigma^*$ is a regular language over
any alphabet $\Sigma$, then $L' = \{a^m \mid \exists w \in L \ni |w| = m\}$ is a regular language.\\

Noting that $L'$ is a language consists of one-letter strings which respectively has the same length of strings in $L$, which means $|L'| = |L|$. The proof is actually trivial. Let $D$ be a DFA accepts $L$, we just mark each label in $D$ with letter $a$, and we get a DFA accepts $L'$.\\

From (ii)(a) we know $L'$ is regular language iff the set $|L'|$ is ultimately periodic. And we have $|L'| = |L|$. Hence $|L|$ is ultimately periodic.

\vspace {0.25cm}\noindent
{\bf Solution B2}\\

\vspace {0.25cm}\noindent
(a) (i) $\forall x,y\in \Sigma^*$, if $x\approx y$ then $\forall
p\in Q$, $\delta^*(p,x)\in F$ iff $\delta^*(p,y)\in F$. $\forall
w\in\Sigma^*$,
\[\delta^*(p, wx)\in F=\delta^*(\delta^*(p,w),x)\in F\Rightarrow \delta^*(\delta^*(p,w),y)\in F=\delta^*(p, wy)\in
F.\] In the same way, $\delta^*(p, wy)\in F\Rightarrow \delta^*(p,
wx)\in F$. That is $wx\approx wy$, which means $\approx$ is left-invariant.\\

\vspace {0.25cm}\noindent
(a) (ii) $\forall x,y\in\Sigma^*$, if $x\sim y$ then $\forall p\in Q,
\delta^*(p,x)=\delta^*(p,y)$. $\forall w\in\Sigma^*$,
\[\delta^*(p,wx)=\delta^*(\delta^*(p,w),x)=\delta^*(\delta^*(p,w),y)=\delta^*(p,wy).\]
That is $wx\sim wy$, which means $\sim$ is left-variant. In the same
way we can have $\sim$
is right-variant. So $\sim$ is both left and right invariant.\\

\vspace {0.25cm}\noindent
(b) (i) $\forall x\in\Sigma^*$, construct a vector
$(b_1,b_2,\cdot\cdot\cdot,b_n)_x$, in which $b_i=1$ iff
$\delta^*(q_i,x)\in F$ and $b_i=0$ iff $\delta^*(q_i,x)$ does not
belong to $F$. By definition, $x\approx y$ iff
$(b_1,b_2,\cdot\cdot\cdot,b_n)_x=(b_1,b_2,\cdot\cdot\cdot,b_n)_y$.
Since $(b_1,b_2,\cdot\cdot\cdot,b_n)$ has at most $2^n$ states so
$\approx$ has at most $2^n$ equivalences.\\

\vspace {0.25cm}\noindent
(b) (ii) $\forall x\in\Sigma^*$, construct a vector
$(b_1,b_2,\cdot\cdot\cdot,b_n)_x$, in which $b_i=j$ iff
$\delta^*(q_i,x)=q_j$. By definition, $x\sim y$ iff
$(b_1,b_2,\cdot\cdot\cdot,b_n)_x=(b_1,b_2,\cdot\cdot\cdot,b_n)_y$.
Since $(b_1,b_2,\cdot\cdot\cdot,b_n)$ has at most $n^n$ states so
$\sim$ has at most $n^n$ equivalences.\\

\vspace {0.25cm}\noindent
(c) (i) $\forall u,v\in\Sigma^*$, if $u\lambda_L v$ then
$\forall z\in\Sigma^*$, $zu\in L$ iff $zv\in L$. $\forall w\in
\Sigma^*$, $zwu\in L=(zw)u\in L\Rightarrow (zw)v\in L=zwv\in L$. In
the same way, $zwv\in L\Rightarrow zwu\in L$. That is $wu\lambda_L
wv$, which means $\lambda_L$ is left-invariant.\\

\vspace {0.25cm}\noindent
(c) (ii) $\forall u,v\in\Sigma^*$, if $u\mu_L v$ then $\forall
x,y\in\Sigma^*$, $xuy\in L$ iff $xvy\in L$. $\forall w\in\Sigma^*$,
$xuwy\in L=xu(wy)\in L\Rightarrow xv(wy)\in L=xvwy\in L$. That is
$uw\mu_L vw$, so $\mu_L$ is right-invariant. In the same way we have
$xwuy\mu_L xwvy$, which means $\mu_L$ is also left-invariant.\\

\vspace {0.25cm}\noindent
(c) (iii)\\

(1) $\forall u,v\in\Sigma^*$, $u\lambda_Lv$ means $\forall z\in
\Sigma^*$ ($zu\in L$ iff $zv\in L$). Let $p=\delta^*(q_0,z)$, we
have ($\delta^*(p,u)\in F$ iff $\delta^*(p,v)\in F$), which is
$u\approx v$. So $u\lambda_L v \Rightarrow u\approx v$.\\

In the other way, if $u\approx v$ then $\forall p\in Q$
($\delta^*(p,u)\in F$ iff $\delta^*(p,v)\in F$). Since $\exists
z\in\Sigma^*$ that $\delta^*(q_0,z)=p$, we have ($zu\in L$ iff
$zv\in L$), which is $u\lambda_L v$. So $u\approx v\Rightarrow
u\lambda_L v$. Therefore we have ($u\lambda_L v$ iff $u\approx v$),
which means $u\lambda_L v$ has the same upper bound of equivalences
as $u\approx v$, which is $2^n$. So $\lambda_L$ has finite number of
equivalence classes.\\

(2) $\forall u,v\in\Sigma^*$, $u\mu_L v$ means $\forall
x,y\in\Sigma^*$, $xuy\in L$ iff $xvy\in L$. Since $L$ is regular,
let $D$ be a DFA accepting $L$. Let $p=\delta^*(q_0, x)$, and
$p_1=\delta^*(p, u)$, $p_2=\delta^*(p, v)$. If $p_1\neq p_2$, since
$\forall y\in\Sigma^*$ that ($\delta^*(p_1,y)\in F$ iff
$\delta^*(p_2,y)\in F$), so $D$ can be simplified by combining
$p_1,p_2$. $\forall u,v\in\Sigma^*$, $u\mu_L v$, after all such
possible simplifications, let $p=\delta^*(q_0,x)$, then
$\delta^*(p,u)=\delta^*(p,v)$, which is $u\sim v$. This means
$\mu_L$ has the same number of equivalences as $\sim$, which is
$2^{n^n}$. Therefore $\mu_L$ has finite number of equivalence
classes.

\vspace {0.25cm}\noindent
{\bf Solution B3.}

\vspace {0.25cm}\noindent
(a) Proof:\\

Since $L$ is a regular language, there is a DFA $D$ accepting $L$, and using $D$, similar to \textbf{Problem 2}, we define an equivalent relation $\sim$. For all the string $u,v$ in $L$, we have $u \sim v$. We have already prove that $\sim$ is both left-invariant and right-invariant, then we can have if $u \sim v$, then $u^k \sim v^k$. We can have $L^3$ is the union of some of the equivalence classes of equivalence relation $\sim$, which is right-invariant and has finite index. $L^3$ is regular.\\

We also have, for all the string $u$ in $L^{(1/3)}$, if $u \sim v$, $v \in L^{(1/3)}$. Then $L^{(1/3)}$ is the union of some of the equivalence classes of equivalence relation $\sim$, which is right-invariant and has finite index. We conclude that $L^{(1/3)}$ is regular.

\vspace {0.25cm}\noindent
(b) Proof:\\

Similar to (a), we have, for all the string $u$ in $L^{(1/k)}$, if $u \sim v$, $v \in L^{(1/k)}$. Then $L^{(1/k)}$ is the union of some of the equivalence classes of equivalence relation $\sim$, which is right-invariant and has finite index. We conclude that $L^{(1/k)}$ is regular.\\

In \textbf{Problem 2}, we show that $\sim$ has at most $n^n$ equivalences. So, considering all the possibility of the union of equivalence classes, there are at most $2^{n^n}$ languages of the form $L^{(1/k)}$.

\vspace {0.25cm}\noindent
(c) Proof:\\

Both $L^{1/\infty}$ and $\sqrt{L}$ are regular, it is trivial to prove that they are also the union of some of the equivalence classes of equivalence relation $\sim$.\\

$L^{\infty}$ might not be regular.

\vspace {0.25cm}\noindent
{\bf Solution B4.}

\vspace {0.25cm}\noindent
(a) $L_1$ is not regular. Proof:
\begin{itemize}
    \item For every $m \geq 1$, let string $w'=wcw$, and $|w'|=2m+1$.
    \item For every decomposition $w'=uxv$, $x \neq \epsilon$, $|ux| \leq m$, we can have $v=ycw$, $|y| \geq 0$.
    \item We can see for any $i \geq 0$, $ux^iy \neq w$, then $ux^iv \notin L(D)$.
\end{itemize}
According to pumping lemma, we conclude that $L_1$ is not regular.

\vspace {0.25cm}\noindent
(b) $L_2$ is not regular. Proof:
\begin{itemize}
    \item For every $m \geq 1$, let string $w=xy$, and $|w|=2m$.
    \item For every decomposition $w=uxv$, $x \neq \epsilon$, $|ux| \leq m$, we can have $v=sy$, $|s| \geq 0$.
    \item For any $x$, we can choose i, so that $|u|+|x|*i+|v| $ is odd, then $ux^iv \notin L(D)$.
\end{itemize}
According to pumping lemma, we conclude that $L_2$ is not regular.

\vspace {0.25cm}\noindent
(c) $L_3$ is not regular. Proof by contradiction:\\

Assume $L_3$ is regular. By pumping lemma, there exists a  decomposition of $\omega$ as $\omega = uxv$ where $\forall i \geq 0, ux^iv \in L_3$.
Say $\omega = a^m,\ m \in P$ and $x = a^n, n \geq 1$. Then let $i = m + 1$, we have $ux^iv = a^{(m-n)+in} = a^{m-n+(m+1)n} = a^{m(n+1)} \in L_3$. Notice that $n+1 \geq 2$ and $m \in P$, so $m(n+1)$ cannot be a prime number. This contradicts the fact that $ux^iv \in L_3$. Assumption fails. Hence $L_3$ is not regular.

\vspace {0.25cm}\noindent
(d) $L_4$ is not regular. Proof:
\begin{itemize}
    \item For all strings $a^{17m}b^{17m}$, m is prime number. There must be two strings $a^{17m_1}b^{17m_1}$ and $a^{17m_2}b^{17m_2}$ belong to the same equivalent class.
    \item Let $z=b^{17m_1}$, then $a^{17m_1}b^{34m_1}$, $a^{17m_1}b^{17(m_1+m_2)}$.
    \item Then we have $xz \in L_4$, and $yz \notin L_4$.
\end{itemize}
According to Theorem 2.17.4, we conclude that $L_4$ is not regular.

\vspace {0.25cm}\noindent
{\bf Solution B5.}

\vspace {0.25cm}\noindent
(a) Proof: \\

Since $L_1$ and $L_2$ are two regular languages, there exists two DFA $D_1=(Q_1,\Sigma,\delta_1,q_{01},F_1)$, $D_2=(Q_2,\Sigma,\delta_2,q_{02},F_2)$ to accept $L_1$ and $L_2$ respectively. Then we can construct DFA $D=(Q,\Sigma,\delta,q_{0},F)$, which $Q=Q_1 \times Q_2$, $q_0=(q_{01},q_{02})$, $F=F_1 \times F_2$, $\delta((q_1,q_2),a)=(\delta_1(q_1,a),\delta_2(q_2,a))$.\\

As Definition $2.17.1$, we can define the relation $\cong_D$ using DFA $D$, it is similar to show that $\cong_D$ is an equivalence relation, which is also right-invariant. Every state in $Q$ is an equivalence class, we denote it as $[q]$ and $L_1 \cap L_2$ is the union of all the equivalence classes $[f],f \in F$. The number of equivalence classes of $\cong_D$ is finite, according to \textbf{Myhill-Nerode}, $L_1 \cap L_2$ is also regular language.

\vspace {0.25cm}\noindent
(b) Proof: \\

Since $L'$ is a regular language, there exists a DFA $D=(Q,\Sigma,\delta,q_{0},F)$ to accept $L'$. We define the relation $\cong_D$ on $\Sigma^*$, for any two string $u,v \in \Sigma^*$,\\

\begin{center}
$ u \cong_D v$ iff $\delta^*(q_0,h(u)) = \delta^*(q_0,h(v)) $
\end{center}

As Definition $2.17.1$, it is similar to show that $\cong_D$ is an equivalence relation. For any $w \in \Sigma^*$, if $u \cong_D v$, then $\delta^*(q_0,h(u)) = \delta^*(q_0,h(v))$, we can have $\delta^*(q_0,h(u)h(w)) = \delta^*(q_0,h(v)h(w))$, since $\mapdef{h}{\Sigma^*}{\Delta^*}$ is a homomorphism, then $\delta^*(q_0,h(uw)) = \delta^*(q_0,h(vw))$, we have $uw \cong_D vw$. We have $\cong_D$ is right-invariant. Every state in $Q$ is an equivalence class, we denote it as $[q]$ and $h^{-1}(L')$ is the union of all the equivalence classes $[f],f \in F$. The number of equivalence classes of $\cong_D$ is finite, according to \textbf{Myhill-Nerode}, $h^{-1}(L')$ is also regular language.\\

Let the DFA $D$ above to be the minimal DFA accepting $L'$ with number of states $m$, the number of equivalence classes of $\cong_D$ is $m$. Similar to the proof of \textbf{Lemma 2.17.3}, we can construct a DFA $D'$ to accept $h^{-1}(L')$ with $m$ states, so the  number of states of any minimal DFA for $h^{-1}(L')$ is at most the number of states of any minimal DFA for $L'$. \\

It cannot be strictly smaller, since the DFA $D'$ above could be a minimal DFA for $h^{-1}(L')$ itself.\\

\vspace{0.25cm}\noindent
\noindent {\bf Solution B6}

\vspace{0.25cm}\noindent
(i)(a)\\
Notice that any relation $R\subseteq Q\times Q$ is a subset of $\{(p,q) \mid (p,q) \in Q\times Q\}$. By definition of DFA, $Q$ should has finitely many states, say $n$ states in all. So $\{(p,q) \mid (p,q) \in Q\times Q\}$ is a finite set which contains at most $n\times n$ orderred pairs. \\
Notice that $R_{i} \cup \{(\delta(p, a), \delta(q, a))\ |\ (p, q)\in R_i,\ a\in \Sigma\}$ is no smaller than $R_i$, but we already know $R_i$ is a subset of some finite set, which implies it cannot grow infinitely. So at some point, there exists an $i_0$ such that:\\
$$R_{i_0} = R_{i_0} \cup \{(\delta(p, a), \delta(q, a))\ |\ (p, q)\in R_{i_0},\ a\in \Sigma\}$$
So $R_{i_0+1} = (R_{i_0})_{\approx}$. Notice that $R_{i_0}$ is some equivalence relationship in following form:
$$R_{i} = (R_{i-1} \cup \{(\delta(p, a), \delta(q, a))\ |\ (p, q)\in R_{i-1},\ a\in \Sigma\})_{\approx}$$
Simply denote $R_i = (R')_{\approx}$. So we have $R_i = (R')_{\approx} = (R' \cup R'^{-1})^*$. And $R_{i_0+1} = (R_{i_0})_{\approx} = (R \cup R^{-1})^* = ((R' \cup R'^{-1})^* \cup {(R' \cup R'^{-1})^*}^{-1})^* = ((R' \cup R'^{-1})^*)^* = (R' \cup R'^{-1})^* = R_{i_0}$. Hence we found $R_{i_0+1} = R_{i_0}$ for some least $i_0$.

\vspace{0.25cm}\noindent
(b)
It follows from (a) that $$R_{i_0} = (R_{i_0} \cup \{(\delta(p, a), \delta(q, a))\ |\ (p, q)\in R_{i_0},\ a\in \Sigma\})_{\approx}$$
It is trivial to show that $R_{i_0}$ is a forward closure containing $R$. In fact whenever $(p,q) \in R_{i_0}$, then $(\delta(p, a), \delta(q, a))\in R_{i_0}$, for all $a\in\Sigma$. And since $R_0$ is the smallest equivalence relation containing $R$, it is clear that $R_{i_0}$ contains $R$.

We start from $R_0$ which is the smallest equivalence relation containing $R$, and expand by the rule that $(R_{i} \cup \{(\delta(p, a), \delta(q, a))\ |\ (p, q)\in R_i,\ a\in \Sigma\})_{\approx}$, eventually we reach the $R_{i_0}$ and can no longer expand. It is somehow obvious that at $R_{i_0}$, we get a forward closure containning $R$, and according to our expansion rule, it is the smallest one.   

\vspace{0.25cm}\noindent
(ii) Given $p\equiv q$. If $R^\dagger$ is not good, then
$\exists (p', q')\in R^\dagger$ that only one of $p',q'$ belongs to
$F$, suppose $p'\in F$ and $q'$ does not. Since $\exists
w\in\Sigma^*$ that $\delta^*(p,w)=p'$, by the definition of forward
closure, $\delta^*(q,w)=q'$. From $p\equiv q$ we have
$(\delta^*(p,w)\in F$ iff $\delta^*(q,w)\in F)$. That's $(p'\in F$
iff $q'\in F)$, which contradicts that only one of $p',q'$ belongs
to $F$. So $\forall (p',q')\in R^\dagger$, either both $p',q'$
belong to $F$, or both they don't. That is $(p\equiv q)\Rightarrow$
($R^\dagger$is good.)\\

In another way, given $R^\dagger$ is good. $\forall w\in\Sigma^*$,
let $\delta^*(p,w)=p'$ and let $\delta^*(q,w)=q'$. By definition of
forward closure, $(p',q')\in R^\dagger$. Since $R^\dagger$ is good,
we have $(p'\in F$ iff $q'\in F)$. That is $(\delta^*(p,w)\in F$ iff
$\delta^*(q,w)\in F)$, which means $p\equiv q$. So ($R^\dagger$ is
good) $\Rightarrow (p\equiv q)$.

\end{document}
